Generally, the invention relates to the field of techniques for utilizing computer memory devices when they have compressed data. Specifically, the techniques focus on the field of operating devices so as to access randomly specified portions of such compressed data. It has particular applicability in computer tape drives such as are used in computer peripheral memory backup devices.
Since the advent of programmable data processing systems, or computers, the need to store information has grown dramatically. This information storage is frequently accomplished through devices which interconnect with the computer and act relatively independent of it in response to signals received from the main data processing functions of the computer. These devices, known as peripheral devices, act to receive data from the main computer memory and then to store such data on a separate media associated with the peripheral device.
One of the aspects of typical memory devices in computer systems is their volatility--they can unintentionally lose their contents occasionally. To overcome this undesirable aspect, backup devices have evolved. Such devices serve the simple function of separately storing large amounts of data on relatively non-volatile media. In the field of these specialized devices the use of magnetic tape media has greatly eclipsed all other types of storage media. This use is so broad that magnetic tape cartridges which are specifically designed to be used with computer backup devices have been developed. Such cartridges specifically meet the needs of computer users in a standardized and optimum fashion.
In essence, computer backup devices serve as a separate memory system on which data or information can be stored. As with any type of memory device, there are limitations on the amount of data which the media can hold. While removable media such as magnetic tape cartridges have been developed to allow the users to have virtually unlimited memory capacity, within each cartridge limits still exist. Accordingly, the technique of compressing the data has been developed. Through this technique data can be stored in a form which takes less memory space than as originally stored. In advanced backup devices, the step of compressing the data is usually accomplished automatically by the backup device itself without additional actions by the user.
A variety of techniques for compressing data exist. These algorithms each act uniquely to compress data or files from one size to a smaller size for storage purposes. The data or file in compressed form--that of reduced size--is then stored on the memory media. Because of the way these algorithms work, the reduction in size that any particular amount of data receives varies not only by the type of algorithm used, but also the contents of the data. For this reason, the reduction in size is not predictable.
As with any memory device associated with a computer, accessing such memory is an important element. To accomplish this on any type of memory device, the location of the desired data must first be determined. While this is a straight-forward operation when data is stored in uncompressed form, when compression is included it is more difficult for the simple reason that the amount of compression varies. For the present invention, access to the data also requires the additional step of uncompressing the data or file. Accordingly, the desire to locate and access the data in the shortest amount of time possible has long been a goal of those skilled in the art.
The present invention focuses upon the techniques used to locate and access data stored in compressed form on any type of media. While it is especially appropriate for serially-disposed media such as computer tape memory media, it has applicability to other media as well. Even though the concept of storing compressed data has been well known and even though those in the field of computer backup memory devices have long had to deal with the difficulty of locating data in compressed form, the desire for an efficient access technique has remained unsatisfied until the present invention. This was perhaps due to the fact that the standards which had developed among those involved acted to teach away from the direction of the present invention. As an example, the quarter-inch-cartridge (QIC) recording format standards promoted by the industry teach the use of tables for data location, then a separately generated compression map is utilized to locate the data in traditional manners.
Prior to the present invention those skilled in the art either serially uncompressed data until the appropriate aspect was located, or they relied upon a table look-up technique. In the table look-up technique, an additional step of creating a listing of file size after compression is accomplished. While such a technique does improve the ease with which the location of desired data can be ascertained, several drawbacks exist. First, the creation of the additional table information takes time, adding to the apparent memory access time. Second, additional memory space is required to store the information. Also, update or modification of the table has been difficult to accomplish efficiently.
Other inventions have addressed similar problems, however, they have not been readily adaptable to the problem addressed by the present invention. Rather, they have been directed to techniques to locate items in a listing which is itself compressed. As an example, U.S. Pat. No. 3,651,483 discloses techniques which allow searching a compressed index, not compressed data. Similarly, U.S. Pat. No. 3,643,226 dealt with the same problem in a fashion which is not adaptable to the problems addressed by the present invention.